package com.cat.binaryTree;

import java.util.Arrays;

/**
 *   @description https://leetcode.cn/problems/unique-binary-search-trees/description/?envType=problem-list-v2&envId=xhsq2On3
 *   @author 曲大人的喵
 *   @create 2025/9/13 15:31
 *   @since JDK17
 */

public class Solution25 {
    int []dp;
    int f(int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        if (dp[n] != -1) {
            return dp[n];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += f(i) * f(n - i - 1);
        }
        return dp[n] = ans;
    }
    public int numTrees(int n) {
        dp = new int[n + 1];
        Arrays.fill(dp, -1);
        return f(n);
    }
}
